One requirement for link-sharing is to share bandwidth on a link between multiple organizations, where each organization wants to receive a guaranteed share of the link bandwidth during congestion, but where bandwidth that is not being used by one organization should be available to other organizations sharing the link. Examples range from the multiple agencies that share the Trans-Atlantic FAT pipe and each pay a fixed share of the costs to individuals who share a single ISDN line. Another example of link-sharing is the shared bandwidth on a link between different protocol families (e.g. IP and SNA), where controlled link-sharing is desired because the different protocol families have different responses to congestion. A third example of link-sharing is to share bandwidth on a link between different traffic types, such as telnet, ftp, or real-time audio and video.
The control of network resources involves local decisions on usage as well as considerations of per-connection end-to-end requirements. One function of link-sharing mechanisms is to enable gateways to control the distribution of bandwidth on local links in response to purely local needs.
The need to carry different traffic types including real-time services on the shared links results in a need for hierarchical link sharing having classes of traffic. Link-sharing services and real-time services involve simultaneous sets of constraints to be satisfied at the gateway. There is also a need to prevent starvation of lower-priority traffic while satisfying the needs of higher-priority traffic while meeting link-sharing requirements.
Current scheduling methods support differentiated Quality of Service (QOS) using variations on prioritized Class Based Queuing (CBQ) or a Weighted Fair Queuing (WFQ) approach. Prior art CBQ and WFQ methods ignore two important factors: 1) overlimit traffic, i.e. traffic from a flow that exceeds the flow's committed traffic rate specification, and 2) deliberate “overbooking” of flows in order to provide statistical rather than guaranteed assurance of bandwidth and delays. Overbooking of flows means that flows with reserved minimum bandwidth requirements are admitted even though there is insufficient capacity to provide that bandwidth when all flows are simultaneously active.
The CBQ algorithm depends on a fixed set of flows that are always considered active, rather than an environment of rapidly changing active flows. The CBQ algorithm uses a slow-acting “average” rate per flow to classify it as overlimit. The CBQ algorithm is relatively slow acting, because it relies on a calculated average rate of a class to determine whether the class is above or below a traffic limit. It depends on calculation of relatively slow-acting average rate per flow (or class) to mark the class “overlimit” and then on a relatively complicated algorithm for determining what the “fair” bandwidth allocation to an overlimit class should be. Finally, it makes no provisions for “overbooking” of flows in a class, i.e. where flows with guaranteed minimum service rates are deliberately over-admitted, in the hope that statistically few admitted flows will be simultaneously backlogged. The CBQ algorithm does not discuss class bandwidth enforcement in the presence of overbooking.
With the CBQ algorithm, each class can be limited to its assigned average bandwidth, but there are no protections to the instantaneous loss of bandwidth to underlimit classes. This is because the CBQ algorithm as described relies on the relatively slow-changing average rate to determine whether a class is overlimit or not.
Single-level WFQ methods suffer from the problem of overbooking, because an overbooked set of flows can obtain an arbitrarily large fraction of bandwidth. Each flow consumes its “fair share” even if there are too many of them. The overbooking problem is alleviated with the concept of a hierarchy of WFQ schedulers. The WFQ algorithms, however, assume that each flow obeys its traffic specification, and the algorithm described makes no provision for individual flows that are over the traffic specification limit. There is no concept in the hierarchical WFQ method for a flow in one class to “share” the bandwidth with a best effort class. If one flow of a higher level is overlimit, it must content itself with the bandwidth allocated to its class, and cannot compete with other best-effort flows in the default class. For example, consider a case where there are 5 flows in a “guaranteed” class, each of which is assigned 10% of the bandwidth and only 1 flow in the default class, which is also allocated 50% of bandwidth. The one default flow is continuously backlogged and so is getting 50% of bandwidth. If one of the guaranteed flows suddenly bursts to need as much bandwidth as it can get, it will continue to receive only 10% of the link bandwidth, i.e. ⅕ of the 50% assigned to the guaranteed class using hierarchical WFQ.
In a WFQ scheduling algorithm, overbooked flows will continue to use their weight's worth of bandwidth, and indeed with sufficient overbooking can consume arbitrarily large fractions of the bandwidth. The WFQ algorithm makes no provision for a “class” of flows to be limited to a percentage of bandwidth, and for that bandwidth to be enforced even in the presence of overbooking. Overbooking is an important economic requirement for commercial bandwidth providers. The WFQ algorithm, while providing better worst case delays than a Deficit Round Robin (DRR) algorithm, also has several computational complexities. The chief problems are a divide operation to calculate the “finish time” of a packet, and the complexity in maintaining an ordered queue based on finish time. These complexities are generally considered to be on the order of O(log N) for N possible flows.